#include "PriorityQLow.h"
#include "Scheduler.h"
#include <algorithm>


//  used to swap two values
void Swap(TaskInfo* &a, TaskInfo* &b)
{
	TaskInfo* temp = a;
	a = b;
	b = temp;
}


PriorityQLow::PriorityQLow():m_iSize(0)
{
	m_iMaxSize = 100;
	TaskInfo* pNUll = NULL;
	m_Heap.assign(m_iMaxSize, pNUll);
}

void PriorityQLow::ReorderUpwards(std::vector<TaskInfo*>& heap, int nd)
{
	//move up the heap swapping the elements until the heap is ordered
	while ( (nd>1) && (heap[nd/2]->time.next > heap[nd]->time.next))
	{
		Swap(heap[nd/2], heap[nd]);

		nd /= 2;
	}
}

void PriorityQLow::ReorderDownwards(std::vector<TaskInfo*>& heap, int nd, int HeapSize)
{
	//move down the heap from node nd swapping the elements until
	//the heap is reordered
	while (2*nd <= HeapSize)
	{
		int child = 2 * nd;

		//set child to largest of nd's two children
		if ( (child < HeapSize) && (heap[child]->time.next > heap[child+1]->time.next) )
		{
			++child;
		}

		//if this nd is lager than its child, swap
		if (heap[nd]->time.next > heap[child]->time.next)
		{
			Swap(heap[child], heap[nd]);

			//move the current node down the tree
			nd = child;
		}

		else
		{
			break;
		}
	}
}

bool PriorityQLow::empty()
{
	return (m_iSize==0);
}

void PriorityQLow::insert(TaskInfo* item)
{
	//assert (m_iSize+1 <= MAXSIZE);

	if (m_iSize + 1 >= m_iMaxSize)
	{
		m_iMaxSize *= 2;
		std::vector<TaskInfo*> temp = m_Heap;
		TaskInfo* pNUll = NULL;
		m_Heap.assign(m_iMaxSize, pNUll);
		std::copy(temp.begin(), temp.end(),m_Heap.begin());
	}

	++m_iSize;

	m_Heap[m_iSize] = item;

	ReorderUpwards(m_Heap, m_iSize);
}

TaskInfo* PriorityQLow::pop()
{
	Swap(m_Heap[1], m_Heap[m_iSize]);

	ReorderDownwards(m_Heap, 1, m_iSize-1);

	TaskInfo* ret = m_Heap[m_iSize];

	//remember to reset the pointer!! or complex bugs!
	m_Heap[m_iSize] = NULL;
	m_iSize--;
	return ret;
}

TaskInfo* PriorityQLow::peek()
{
	return m_Heap[1];
}

void PriorityQLow::Erase(std::vector<TaskInfo*>::iterator itr)
{
	m_Heap.erase(itr);
	m_iSize--;
	ReorderDownwards(m_Heap, 1, m_iSize);
}

std::vector<TaskInfo*>::iterator PriorityQLow::Begin()
{
	return m_Heap.begin() + 1;
}

std::vector<TaskInfo*>::iterator PriorityQLow::End()
{
	return m_Heap.end();
}